package com.s6.sort1;

/**
 * 插入排序，array 表示数组, 比冒泡排序应用更广泛
 */
public class InsertionSort {

	public static void main(String[] args) {
		int[] array = ArrayUtils.randomInt();
		ArrayUtils.print(array);
		sort(array);
		ArrayUtils.print(array);
	}

	public static void sort(int[] array) {
		int j, max;
		for (int i = 1; i < array.length; i++) {
			max = array[i];
			// 查找插入的位置
			for (j = i - 1; j >= 0; j--) {
				// 移动
				if (array[j] > max) {
					array[j + 1] = array[j];
				} else {
					break;
				}
			}
			// 此时 array[j] <= max, // 插入数据
			array[j + 1] = max;
		}
	}

}
